package sort;

/**
 * 归并排序，时间复杂度用master公式算，O（NlogN）,空间复杂度为O(N)
 * master公式
 *  T（N） = a*T（N/b） + O（N^d）
 *
 *  log(b,a) > d --> 复杂度为O(N^log(b,a))
 *  log(b,a) = d --> 复杂度为O(N^d*logN)
 *  log(b,a) < d --> 复杂度为O(N^d)
 */
public class MergeSort {

    //递归将无序数组分成左右两边有序
    public static void process(int[] arrs,int L, int R){
        if (L==R){
            return ;
        }
        //判断数组中点，》右移一位即是除以2
        int mid = L + ((R-L) >> 1);
        //左侧排好序
        process(arrs,L,mid);
        //右侧排好序
        process(arrs,mid+1,R);
        //合并数组
        merge(arrs,L,mid,R);
    }

    private static void merge(int[] arrs, int l, int mid, int r) {
        //辅助数组
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        //判断：左边小于右边则将左边放入辅助数组中，反之同理
        while(p1 <= mid && p2 <=r){
            help[i++] = arrs[p1] <= arrs[p2] ? arrs[p1++] : arrs[p2++];
        }
        //越界之后则将，不越界的数组全量拷贝
        {
            while (p1 <= mid) {
                help[i++] = arrs[p1++];
            }
            while (p2 <= r) {
                help[i++] = arrs[p2++];
            }
        }
        //赋值回原数组
        for (int j = 0; j < help.length; j++) {
            arrs[l+j] = help[j];
        }
    }

    public static void main(String[] args) {
        int[] arrs = {1,3,5,7,2,5,8,4};
        process(arrs,0,arrs.length-1);
        for (int arr : arrs) {
            System.out.println(arr);
        }
    }
}
